package 动态规划专项训练.动态规划训练2;

/**279. 完全平方数
 * @author zx
 * @create 2022-04-19 9:52
 */
public class Num279 {
    public int numSquares(int n) {
        int[] f = new int[n + 1];
        f[0] = 0;
        for(int i = 1;i <= n;i++){
            f[i] = Integer.MAX_VALUE;
            for(int j = 1;j * j <= i;j++){
                if(f[i - j * j] + 1 < f[i]){
                    f[i] = f[i - j * j] + 1;
                }
            }
        }
        return f[n];
    }
}
